package leetcode_2601_2700;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_2602 {
    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{3, 1, 6, 8}, new int[]{1, 5}));
    }
    private static List<Long> minOperations(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] sums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int m = queries.length;
        List<Long> ans = new ArrayList<>();
        for (int query : queries) {
            int index = 0, r = n - 1;
            index = getI(nums, query, index, r);
            int c1 = index + 1;
            int c2 = n - c1;
            long res = (long) c1 * query - sums[index + 1] + (sums[n] - sums[index + 1]) - (long) c2 * query;
            ans.add(res);
        }
        return ans;
    }

    private static int getI(int[] nums, int query, int l, int r) {
        while (l < r){
            int mid = (l + r + 1) / 2;
            if (nums[mid] <= query){
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        if (nums[l] > query){
            return -1;
        }
        return l;
    }
}
